//151.反转字符串中的单词
//https://leetcode.cn/problems/reverse-words-in-a-string/
class Solution {
public:
    string reverseWords(string s) {
        int n = s.size();
        int start = 0;
        int end = n-1;
        while(start < n && s[start] == ' ') ++start; 
        while(end >= 0 && s[end] == ' ') --end;
        if(start >= end) return s.substr(0,end-start+1);
        string ret;
        ret.reserve(n);
        while(start <= end) 
        {
            if (ret.size() > 0 && ret.back() == ' ' && s[end] == ' ')
            {
                --end;
                continue;
            }
            ret.push_back(s[end--]);
        }

        //开始区间反转
        start = 0;
        end = ret.size();
        int pos = 0;
        while(start < end)
        {
            while(pos < end && ret[pos] != ' ') ++pos;
            for(int i = start,k=pos-1;i<k;++i,--k) swap(ret[i],ret[k]);
            start = ++pos;
        }
        return ret;
    }
};